package 剑指offer;


/*
 * Author：江松
 * Date：2023/3/17 22:36
 *
 链表中环的入口：
 1：哈希表去重
 2：双指针---快慢指针，
 判断是否成环：有环就是追及问题，速率不同肯定相遇。
 找点：根据交点找入口，
 简单理解:快指针多走一圈
 快指针：A->B(入口)->C(交点)->B->C=2*(X+Y)
 慢指针：A->B->C      所以C->B=X=A->B的距离

 官方题解：更合理
 假设快指针走了n圈环，慢指针走了m圈环，才相交（因为计算机是离散的）
快指针走了x+y+n(y+z)=2*(x+y+m(y+z))慢指针的路程
则有，x+y=(n−2m)(y+z)。说明链表头经过环入口到达相遇地方经过的距离等于整数倍环的大小
(k-1)y+kz=x,y路程是共同的，说明x=nz会在入口相遇
 */

import java.util.HashMap;
import java.util.HashSet;

public class Main37 {
    class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public  ListNode jd(ListNode head){
        ListNode fast=head,slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow)return slow;
        }
        return null;
    }

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        //交点
        ListNode slow=jd(pHead);
        if(slow==null)return null;
        //起点
        ListNode fast=pHead;
        while(slow!=null&&fast!=null){
            if(slow==fast)return slow;
            slow=slow.next;
            fast=fast.next;
        }
        return null;
    }

    public static void main(String[] args) {

    }
}
